package solutions.face.normal;

import java.util.PriorityQueue;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/smallest-k-lcci/">面试题 17.14. 最小K个数</a>
 */
public class Solution17_14 {

    public int[] smallestK(int[] arr, int k) {
        int[] rst = new int[k];
        if (k == 0) {
            return rst;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int v : arr) {
            if (priorityQueue.size() < k) {
                priorityQueue.offer(v);
            } else {
                if (v < priorityQueue.peek()) {
                    priorityQueue.poll();
                    priorityQueue.offer(v);
                }
            }
        }
        int p = 0;
        while (!priorityQueue.isEmpty()) {
            rst[p++] = priorityQueue.poll();
        }
        return rst;
    }

    public static void main(String[] args) {
        Solution17_14 solution = new Solution17_14();
    }
}
